TweetFollow Us on Twitter

Mar 01 Challenge Volume Number: 17 (2001)
Issue Number: 3
Column Tag: Programmer's Challenge

Programmer's Challenge

By Bob Boonstra, Westford, MA

DragSort

I'll confess. I've done it. More than once, actually. It's probably not legal, strictly speaking. But how bad can it be. I mean, lots of people must do it. It's not something truly evil like, well, like Napster.

What am I talking about? Downloading music. From the internet. Music that other people posted, music that I haven't purchased. Yet, that is. Music posted to the UseNet alt.binaries.sounds.* newsgroups.

What does this have to do with the Programmer's Challenge? Downloading Usenet binaries is a (perhaps contrived) motivation for this month's problem, that of sorting a list of items in a particular way. Large binaries are posted in a sequence of parts, and newsreaders thread the parts based on sequence information included by convention in the subject line. But sometimes the subject line contains information that confuses the sequencing, meaning that the parts need to be sorted manually before the binary information can be extracted. With the newsreader I use, the parts are sorted by dragging items from one position in the list to another position, until the parts appear in the correct order.

Your Challenge is to find an efficient way to perform this sort. Efficient in this case means minimizing the amount of tiresome clicking and dragging needed to put the parts in the correct order. Specifically, you want to minimize the cumulative number of positions that you need to move to select the part to be dragged, and the number of positions you need to drag the parts. An example in a later paragraph will make this a little clearer.

Oh, and before you turn me in to the authorities, downloading music from the internet allows one to sample the music before deciding whether to buy it. We all, of course, buy what we keep.

The prototype for the code you should write is:

typedef struct Move {      /* describes moves used to sort itemsToSort */
   long selectPosition;   /*   select this item in the array, origin 0 */
   long dragToPosition;   /*   drag selected item to this position in the array, origin 0 */
} Move;

long /* numMoves */ DragSort(
   long itemsToSort[],         /* array of items to be sorted */
   long numItemsToSort,      /* number of itemsToSort */
   long startPosition,         /* item initially selected */
   Move sortMoves[]            /* store Moves that sort the array here */
);

Your DragSort routine will be called with a list of itemsToSort, a count of the number of items in the list (numItemsToSort), and the element of the list initially selected (selectPosition). DragSort should calculate a sequence of Moves that reorder the list into ascending order by moving the item located at one position in the list (selectPosition) to another position in the list (dragToPosition). Moves are returned in the sortMoves array, and the number of Moves needed to sort the array should be returned by DragSort.

Sounds simple and boring, right? The catch is in how your sort solution is scored. You are penalized one point for each position move your solution makes while performing the sort - one point for each position between your current location and the selectPosition of the next Move, and one point for each position between that selectPosition and the dragToPosition. When a Move is completed, your current position is the dragToPosition. The penalty for the next Move is the number of positions between the previous dragToPosition and the current selectPosition, plus the distance from the current selectPosition and the current dragToPosition, etc.

Imagine, for example, that you are asked to sort the following list, with a startPosition of 0:

            6 1 2 3 5 4

You might employ a bubble sort. Your first Move is to select the 2nd item in the list and move it to the 1st position, at a cost of two penalty points (moving from [0] to [1], and dragging from [1] to [0]). The list now looks like this:

            1 6 2 3 5 4

Next you might move the 3rd item to the 2nd position, at a cost of 3 penalty points (moving from [0] to [2], and dragging from [2] to [1]), leaving the list like this:

            1 2 6 3 5 4

Then you might move the 4th item to the 3rd position, at a cost of 3 more penalty points. Then the 6th item to the 4th position (cost 5 points), and the 6th item to the 5th position (cost 3 points). The list would then be correctly sorted, at a cost, if I have counted correctly, of 16 points.

And you would lose the Challenge.

A more successful contestant would sort the list at a cost of 7 points as follows:

            6 1 2 3 5 4
            1 2 3 5 4 6 (cost 5 points)
            1 2 3 4 5 6 (cost 2 points)

In addition to the points incurred for dragging list items around, a penalty of 1 point will be assessed for each millisecond of execution time. The winner will be the entry that correctly sorts a sequence of lists while accumulating the fewest penalty points. The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal. You may provide a solution in Java instead, provided you also provide a test driver equivalent to the C code provided on the web for this problem.

Three Months Ago Winner

Congratulations to Tom Saxton for winning the December Crutches Challenge. Motivated by a broken foot injury to a member of the family, this variation on the traveling salesperson problem required contestants to find optimal way of moving a set of objects from one location to another, operating with connectivity constraints among the locations, and limited by a maximum carrying capacity. The object was to minimize a score that was a combination of the length of the path traversed and the amount of execution time required to complete the solution. Tom's entry was not the fastest, but it did compute a more optimal path than the second-place entry by Ernst Munter.

Tom first calculates the distance from each node to each other node in the _MapConnections function. He then calculates a baseline solution in the _CatCrutchesCore routine, a solution that picks up the closest object when nothing is being carried, delivers the closest object when something is being carried, and tries to move objects closer to their eventual destination when there is spare carrying capacity. Tom then successively refines the baseline solution until a time allocation is exceeded. Refinement uses a variant of the "Algorithm of the Gods", published in Scientific American in March, 1997 (see http://www.scientificamerican.com/0397issue/0397amsci.html). Basically, the algorithm makes small perturbations in the baseline solution to see if the perturbed solution results in a lower cost.

Ernst's entry was approximately three times faster than Tom's, but it resulted in less optimal solutions. Actually, Ernst's solutions were slightly shorter in approximately half of the test cases, but Tom's were shorter by 1/3 to 1/2 in the larger test cases, giving him the win.

I used 12 test cases for evaluation, where the number of nodes ranged from 10 to 200, the number of connections was as high as 2200, and the number of tasks to be accomplished ranged from 20 for the small graphs to 500 for the larger graphs.

The table below lists, for each of the solutions submitted, the total execution time, the cumulative distance traveled to accomplish all of the delivery tasks, and the number of points earned. As points were incurred based on distance traveled and elapsed time, a smaller number of points was better. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one. The solution marked with an asterisk did not complete the larger problems in a reasonable amount of time.

NameTotal Time (msec)Distance MovedTotal PointsCode SizeData SizeLang
Tom Saxton (165)12773.54568155120188004586C++
Ernst Munter (701)4408.65574775965114852324C++
J. S.***5948344C++

Top Contestants...

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 10 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points
1. Munter, Ernst 281
2. Saxton, Tom 96
3. Maurer, Sebastian 68
4. Rieken, Willeke 65
5. Boring, Randy 52
6. Shearer, Rob 48
7. Taylor, Jonathan 36
8. Wihlborg, Charles 29

... and the Top Contestants Looking For a Recent Win

Starting this month, in order to give some recognition to other participants in the Challenge, we are also going to list the high scores for contestants who have accumulated points without taking first place in a Challenge. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

9. Downs, Andrew 12
10. Jones, Dennis 12
11. Day, Mark 10
12. Duga, Brady 10
13. Fazekas, Miklos 10
14. Flowers, Sue 10
15. Sadetsky, Gregory 10
16. Selengut, Jared 10
17. Strout, Joe 10
18. Hala, Ladislav 7
19. Miller, Mike 7
20. Nicolle, Ludovic 7
21. Schotsman, Jan 7
22. Widyyatama, Yudhi 7
23. Heithcock, JG 6

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Tom's winning Crutches solution:

Crutches.cpp
Copyright © 2000
Tom Saxton
//
// Crutches Challenge Solution, December 2000.
// (c) 2000, Tom Saxton
//
#include "Crutches.h"

#include <Events.h>

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// the basics
enum { fFalse = 0, fTrue = 1 };

// disable asserts
#define Assert(f)

// how long should we spend trying to find a better answer?
#define dtickSecond 60
#define dtickMax (1*dtickSecond)

// random
static unsigned short URand(unsigned short uMac);

// heapsort
typedef unsigned long INDEX;
typedef int (*PFNCMP)(INDEX i1, INDEX i2, void *pv);
extern void HeapSort(void *prgfoo, INDEX iMac, int cbFoo, PFNCMP pfncmp);

// maximum distance value
#define distMax 0x7FFFFFFF

// structures for mapping problem to node indices
typedef struct TSK TSK;
struct TSK
{
   long itaskObject;
   long inodeStart;
   long inodeCur;
   long inodeDst;
   long wgt;
   int  fWanted;
   long rankDrop;
   TSK  *ptskNext;
};

typedef struct ENODE ENDOE;
struct ENODE
{
   long inode;
   Node node;
   long cobj;
   long rankGrab;
};

// connection map stuff
typedef struct CONN CONN;
struct CONN
{
   // base information for this connection
   long inode1;
   long inode2;
   long dist;
};

typedef struct CMAP CMAP;
struct CMAP
{
   long distDirect;
   long distPath;
};

typedef struct NODC NODC;
struct NODC // node connection, used when looking for paths between nodes
{
   long distFromStart;
   int fCheckNeighbors;
};

static CONN *s_paconn;
static long s_cconn;
static CMAP *s_pacmap;
static NODC *s_panodc;

// translation globals
static const Node *s_panode;
static ENODE *s_pdnnode;
static long s_cnode;
static TSK *s_patsk;
static TSK *s_ptskFirst;
static long s_ctsk;
static long s_wgtCarryMost;

// core algorithm stuff
static long _CactCrutchesCore(long inodeStart, Action paact[], 
      long cactMax, long distStop, long *painodePath, 
      long *paitskOrder, long *paitskOrderUsed, long *pdist);
static long _InodeGetTarget(long inodeCur, long cobjCarry, 
      int fUseWantedFlag, long *paitskOrder, long *pcnodeOrderGrab, 
      long *pctskOrderDrop);
static void _RandomizeOrder(long iTry, long cTry, long ctsk, 
      long cnode, const long paitskOrderOld[], 
      long paitskOrderNew[]);

// translation helpers
static long _InodeFromNode(Node node);
static int _CmpEnodeNode(INDEX i1, INDEX i2, void *pv);
static int _CmpEnodeInode(INDEX i1, INDEX i2, void *pv);

// action functions
static int _FTakeStep(long inodeDst, long cactMax, 
   Action paact[], long *pcact, long *pinodeCur, long *pdist);
static int _FFollowPath(long cactMax, Action paact[], 
      long *pcact, long *pinodeCur, long *pwgtCarry, 
long *pcobjCarry, long cnodePath, const long painodePath[]);
static int _FGrabObject(long cactMax, Action paact[], 
   long *pcact, long *pwgtCarry, long *pcobjCarry, long inode, 
      long itsk);
static int _FDropObject(long cactMax, Action paact[], 
   long *pcact, long *pwgtCarry, long *pcobjCarry, long inode, 
      long itsk);

// connection map functions
static void _MapConnections(long cconn, 
      const Connection paconnection[]);
static void _FreeConnectionMap(void);
static int _FConnectedNodes(long inode1, long inode2, 
      long *pdist);
static long _CnodeFindMinPath(long inodeStart, 
      long inodeEnd, long painodePath[]);
static void _ComputeNodeDistances(long inode);
static long _InodeNearestTask(long inodeCur);
static inline long _DistNodeToNode(long inode1, long inode2)
{
   return s_pacmap[inode2*s_cnode + inode1].distPath;
}

static void _ResetState();
static TSK *_PtskRemoveTsk(TSK *ptsk);

Crutches
long /* actions in solution */ Crutches (
  const Node panode[],                  /* Nodes defining the problem */
  long cnode,                                 /* number of Nodes */
  const Connection paconnection[],   /* Connections between nodes */
  long cconn,                               /* number of Connections */
  const Task patask[],                  /* objects to be moved */
  long ctask,   /* objects to be moved, numbered as index into objectsToMove */
  Node nodeStart,                           /* start from this node */
  Weight wgtCarryMost,            /* maximum weight that you can carry */
  Action paact[],                           /* return your solution here */
  long cactMax                              /* size of solutionPath array */
)
{
   long cactBest = 0;
   long *paitskOrderTry = NULL;
   long *paitskOrderBest = NULL;
   long *paitskOrderUsed = NULL;
   long *painodePathBuffer = NULL;
   
   // start the clock running...
   long tickStart = TickCount();
   
   // allocate the memory buffers we need (_MapConnections also allocates memory)
   try
   {
      s_pdnnode =         new ENODE[cnode];
      s_patsk =           new TSK[s_ctsk = ctask];
      paitskOrderTry =    new long[ctask+cnode];
      paitskOrderBest =   new long[ctask+cnode];
      paitskOrderUsed =   new long[ctask+cnode];
      painodePathBuffer = new long[s_cnode];
   } catch (...) {
         printf("Bob, can I have some more memory?
            I need %ld bytes, plus some more for the 
                  connections map.\n",
          sizeof(ENODE)*cnode
         +sizeof(TSK)*ctask
         +sizeof(long)*(ctask+cnode)*3
         +sizeof(long)*s_cnode
         );
      throw;
   }
   if (s_pdnnode == NULL || s_patsk == NULL || 
            paitskOrderUsed == NULL || paitskOrderTry == NULL || 
         paitskOrderBest == NULL || painodePathBuffer == NULL)
      goto LCleanup;

   // initialize the node entry array
   s_cnode = cnode;
   s_panode = panode;
   for (long inode = 0; inode < cnode; ++inode)
   {
      ENODE *penode = &s_pdnnode[inode];
      penode->inode = inode;
      penode->node = panode[inode];
      penode->cobj = 0;
   }

   // sort node entries by node value
   HeapSort(s_pdnnode, cnode, sizeof(s_pdnnode[0]), 
               _CmpEnodeNode);
   
   // fill in TSK records, with inode values
   for (long itask = 0; itask < ctask; ++itask)
   {
      TSK *ptsk = &s_patsk[itask];
      const Task *ptask = &patask[itask];
      
      ptsk->itaskObject = itask;
      ptsk->inodeStart = _InodeFromNode(ptask->fromNode);
      ptsk->inodeDst = _InodeFromNode(ptask->toNode);
      ptsk->wgt = ptask->weight;
   }
   
   _MapConnections(cconn, paconnection);
   
   long inodeStart = _InodeFromNode(nodeStart);
   
   // sort node entries by node index
   HeapSort(s_pdnnode, cnode, sizeof(s_pdnnode[0]), 
               _CmpEnodeInode);
   
   // get the baseline solution
   _ResetState();
   s_wgtCarryMost = wgtCarryMost;
   long distBest;
   cactBest = _CactCrutchesCore(inodeStart, paact, cactMax, 
         distMax, painodePathBuffer, NULL, paitskOrderUsed, 
         &distBest);

   // if we have a non-trivial number of tasks, try to improve our solution using partial 
   // ordering info from the baseline
   // based loosely on "Algorithm of the Gods", Scientific American, March 1997
   if (ctask > 2)
   {
      long distToAccept = distMax;
      long cIter = 0;
      long cIterMax = 10 * cconn * ctask;
      long dtickNext = 0;

      BlockMove(paitskOrderUsed, paitskOrderBest, 
               sizeof(paitskOrderBest[0])*(ctask+cnode));

      for (long dtick = TickCount(); 
            (dtick -= tickStart) < dtickMax && cIter < cIterMax; 
            ++cIter, dtick = TickCount())
      {
         _ResetState();
         
         _RandomizeOrder(dtick, dtickMax, ctask, cnode, 
               paitskOrderBest, paitskOrderTry);
         
         long distTry;
      long cact = _CactCrutchesCore(inodeStart, paact+cactBest, 
               cactMax-cactBest, distToAccept, painodePathBuffer, 
               paitskOrderTry, NULL, &distTry);
         if (distTry < distToAccept)
         {
            distToAccept = distTry;
            BlockMove(paitskOrderTry, paitskOrderBest, 
               sizeof(paitskOrderBest[0])*(ctask+cnode));
            
            if (distTry < distBest)
            {
               distBest = distTry;
      BlockMove(paact+cactBest, paact, cact*sizeof(paact[0]));
               cactBest = cact;
            }
         }
      }
   }

LCleanup:
   _FreeConnectionMap();
   if (s_patsk != NULL)
   {
      delete s_patsk;
      s_patsk = NULL;
   }
   if (s_pdnnode != NULL)
   {
      delete s_pdnnode;
      s_pdnnode = NULL;
   }
   if (paitskOrderTry != NULL)
      delete paitskOrderTry;
   if (paitskOrderBest != NULL)
      delete paitskOrderBest;
   if (paitskOrderUsed != NULL)
      delete paitskOrderUsed;
   if (painodePathBuffer != NULL)
      delete painodePathBuffer;
   
   return cactBest;
}

_CactCrutchesCore
// core function to computer a solution, possibly using a partial node/task ordering array
static long _CactCrutchesCore(
   long inodeStart,
   Action paact[],
   long cactMax,
   long distStop,
   long *painodePath,
   long *paitskOrder,
   long *paitskOrderUsed,
   long *pdist
)
{
   int fSuccess = fFalse;
   long inodeCur = inodeStart;
   long cnodePath = 0;
   long iinodePath = 0;
   long cact = 0;
   long wgtCarry = 0;
   long cobjCarry = 0;
   long inodePath = -1;
   long inodeTarget = -1;
   long cnodeOrderGrab = 0, ctskOrderDrop = 0;

   {
      long iitskRank, iinodeRank;
      
      // reset the priority ranks
      for (iitskRank = 0; iitskRank < s_ctsk; ++iitskRank)
         s_patsk[iitskRank].rankDrop = -1;
      for (iinodeRank = 0; iinodeRank < s_cnode; ++iinodeRank)
         s_pdnnode[iinodeRank].rankGrab = -1;
         
      // if we have a priority order, set task ranks
      if (paitskOrder != NULL)
      {
         for (iitskRank = 0; iitskRank < s_ctsk; ++iitskRank)
         s_patsk[paitskOrder[iitskRank]].rankDrop = iitskRank;
         
      for (iinodeRank = 0; iinodeRank < s_cnode; ++iinodeRank)
            s_pdnnode[paitskOrder[s_ctsk+iinodeRank]].rankGrab = 
                     iinodeRank;
      }
   }
      
   for (long itskCur = *pdist = 0; itskCur < s_ctsk; )
   {
      TSK *ptskT;
      long inodeNext = -1;
      
      // drop any objects whose distination is the current node
      if (cobjCarry > 0)
      {
         for (ptskT = s_ptskFirst; ptskT != NULL; )
         {
   if (ptskT->inodeCur == -1 && ptskT->inodeDst == inodeCur)
            {
            if (!_FDropObject(cactMax, paact, &cact, &wgtCarry,
                      &cobjCarry, inodeCur, ptskT - s_patsk))
                  goto LCleanup;
               inodeTarget = -1;
               ptskT = _PtskRemoveTsk(ptskT);
               ++itskCur;
               continue;
            }
            ptskT = ptskT->ptskNext;
         }
         
         if (itskCur == s_ctsk)
            break;
      }
      
      // see if we want to grab or drop items at this node
      if (s_pdnnode[inodeCur].cobj > 0)
      {
         _ComputeNodeDistances(inodeCur);
         
         // clear the wanted flags for all objects
         for (ptskT = s_ptskFirst; ptskT != NULL; 
                  ptskT = ptskT->ptskNext)
            ptskT->fWanted = fFalse;
            
         long wgtWanted = 0;
         long cobjCarryWanted = 0;
         for(;;)
         {
            // find the object with the nearest desination
            TSK *ptskWant = NULL;
            long distBest = distMax;
            for (ptskT = s_ptskFirst; ptskT != NULL; 
                     ptskT = ptskT->ptskNext)
            {
               if (ptskT->fWanted || 
         (ptskT->inodeCur != inodeCur && ptskT->inodeCur != -1) 
                  || wgtWanted + ptskT->wgt > s_wgtCarryMost)
                  continue;
               
               long distLook;
               if (paitskOrder != NULL)
                  distLook = ptskT->rankDrop;
               else
         distLook = _DistNodeToNode(inodeCur, ptskT->inodeDst);
               if (distLook < distBest)
               {
                  distBest = distLook;
                  ptskWant = ptskT;
               }
            }
         
            // bail if we didn't find anything more to pick up
            if (ptskWant == NULL)
               break;
               
            // mark the new item as wanted
            ptskWant->fWanted = fTrue;
            wgtWanted += ptskWant->wgt;
            cobjCarryWanted += 1;
         }
         
         // did anything change?
         for (ptskT = s_ptskFirst; ptskT != NULL; 
                     ptskT = ptskT->ptskNext)
   if ((ptskT->inodeCur == -1) != (ptskT->fWanted != fFalse))
               break;
         if (ptskT != NULL)
         {
      inodeTarget = _InodeGetTarget(inodeCur, cobjCarryWanted, 
               fTrue/*fUseWantedFlag*/, paitskOrder, &cnodeOrderGrab, 
               &ctskOrderDrop);
            if (inodePath != inodeTarget)
            {
               // make sure we have a path to the current target
               inodePath = inodeTarget;
      if ((cnodePath = _CnodeFindMinPath(inodeCur, inodePath, 
                  painodePath)) == 0)
                  goto LGiveUp;
               iinodePath = 0;
            }
            inodeNext = painodePath[iinodePath];
            
            // clear items that aren't going to be helped by the path to the new target
            for (ptskT = s_ptskFirst; ptskT != NULL; 
                     ptskT = ptskT->ptskNext)
            {
               if (!ptskT->fWanted)
                  continue;
               
               _ComputeNodeDistances(ptskT->inodeDst);
               if (_DistNodeToNode(ptskT->inodeDst, inodeNext) > 
                        _DistNodeToNode(ptskT->inodeDst, inodeCur))
               {
                  ptskT->fWanted = fFalse;
                  wgtWanted -= ptskT->wgt;
                  cobjCarryWanted -= 1;
               }
            }
            
            // drop items we're carrying that we no longer want
            for (ptskT = s_ptskFirst; ptskT != NULL; 
               ptskT = ptskT->ptskNext)
               if (ptskT->inodeCur == -1 && !ptskT->fWanted)
            if (!_FDropObject(cactMax, paact, &cact, &wgtCarry, 
                        &cobjCarry, inodeCur, ptskT - s_patsk))
                     goto LCleanup;
            
            // grab wanted items we're not carrying
            for (ptskT = s_ptskFirst; ptskT != NULL; 
                        ptskT = ptskT->ptskNext)
               if (ptskT->inodeCur == inodeCur && ptskT->fWanted)
            if (!_FGrabObject(cactMax, paact, &cact, &wgtCarry, 
                              &cobjCarry, inodeCur, ptskT - s_patsk))
                     goto LCleanup;
         }
      }
      
      // pick the current target node
      if (inodeTarget == -1)
         inodeTarget = _InodeGetTarget(inodeCur, cobjCarry, 
         fFalse/*fUseWantedFlag*/, paitskOrder, &cnodeOrderGrab, 
               &ctskOrderDrop);
      
      // make sure we have a path to the current target
      if (inodePath != inodeTarget)
      {
         inodePath = inodeTarget;
      if ((cnodePath = _CnodeFindMinPath(inodeCur, inodePath, 
                        painodePath)) == 0)
            goto LGiveUp;
         iinodePath = 0;
      }
      inodeNext = painodePath[iinodePath];
      if (++iinodePath >= cnodePath)
         inodeTarget = inodePath = -1;
      
      // drop any objects not helped by our pending move
      if (cobjCarry > 0)
      {
         for (ptskT = s_ptskFirst; ptskT != NULL; 
                        ptskT = ptskT->ptskNext)
         {
            if (ptskT->inodeCur != -1)
               continue;
            
            _ComputeNodeDistances(ptskT->inodeDst);
            if (_DistNodeToNode(ptskT->inodeDst, inodeNext) > 
                     _DistNodeToNode(ptskT->inodeDst, inodeCur))
            if (!_FDropObject(cactMax, paact, &cact, &wgtCarry, 
                           &cobjCarry, inodeCur, ptskT - s_patsk))
                  goto LCleanup;
         }
      }
      
      // move
if (!_FTakeStep(inodeNext, cactMax, paact, &cact, &inodeCur, 
                     pdist))
         goto LCleanup;
      
      if (*pdist > distStop)
      {
         // fix the object counts
         for (long inodeClean = 0; inodeClean < s_cnode; 
                        ++inodeClean)
            s_pdnnode[inodeClean].cobj = 0;
         goto LGiveUp;
      }
   }
   // set the actual ordering used
   long itskOrder, inodeOrder;
   if (paitskOrderUsed != NULL)
   {
      for (itskOrder = 0; itskOrder < s_ctsk; ++itskOrder)
      {
         TSK *ptskSetOrder = &s_patsk[itskOrder];
         
         if (ptskSetOrder->rankDrop == -1)
            ptskSetOrder->rankDrop = ctskOrderDrop++;
         paitskOrderUsed[ptskSetOrder->rankDrop] = itskOrder;
      }
      for (inodeOrder = 0; inodeOrder < s_cnode; ++inodeOrder)
      {
         ENODE *penode = &s_pdnnode[inodeOrder];
         if (penode->rankGrab == -1)
            penode->rankGrab = cnodeOrderGrab++;
         paitskOrderUsed[s_ctsk+penode->rankGrab] = inodeOrder;
      }
   }
LGiveUp:
   fSuccess = fTrue;
      
LCleanup:
   if (!fSuccess)
      *pdist = distMax;
   return cact;
}

_InodeGetTarget
static long _InodeGetTarget(long inodeCur, long cobjCarry, 
            int fUseWantedFlag, long *paitskOrder, 
            long *pcnodeOrderGrab, long *pctskOrderDrop)
{
   TSK *ptsk;
   // if we have a chosen order, use that
   if (paitskOrder != NULL)
   {
      if (cobjCarry == 0)
      {
         long inodeGrab = -1;
         long rankGrab = s_cnode;
         for (long inode = 0; inode < s_cnode; ++inode)
         {
            ENODE *penode = &s_pdnnode[inode];
            if (penode->cobj == 0)
               continue;
            
            if (penode->rankGrab < rankGrab)
            {
               rankGrab = penode->rankGrab;
               inodeGrab = inode;
            }
         }
         return inodeGrab;
      }
      else
      {
         TSK *ptskChoose = NULL;
         long rankChoose = s_ctsk;
for(ptsk = s_ptskFirst; ptsk != NULL; ptsk = ptsk->ptskNext)
         {
            int fCarried = fUseWantedFlag ? ptsk->fWanted : 
                                                      ptsk->inodeCur == -1;
            
            // only consider carried objects
            if (!fCarried)
               continue;
            
            // pick the one with the lowest rank
            if (ptsk->rankDrop < rankChoose)
            {
               rankChoose = ptsk->rankDrop;
               ptskChoose = ptsk;
            }
         }
         return ptskChoose->inodeDst;
      }
   }
   
   // otherwise if we're not carrying anything, go to the nearest node with an object
   _ComputeNodeDistances(inodeCur);
   if (cobjCarry == 0)
   {
      // pick the nearest node with a task
      long inodeTarget = _InodeNearestTask(inodeCur);
      
      // try to assign a priority to this node
      if (s_pdnnode[inodeTarget].rankGrab == -1)
         s_pdnnode[inodeTarget].rankGrab = (*pcnodeOrderGrab)++;
      return inodeTarget;
   }
   // otherwise deliver the object with the nearest destination
   TSK *ptskDeliver = NULL;
   long distBest = distMax;
for (ptsk = s_ptskFirst; ptsk != NULL; ptsk = ptsk->ptskNext)
   {
   if (fUseWantedFlag ? !ptsk->fWanted : ptsk->inodeCur != -1)
         continue;
   long distLook = _DistNodeToNode(inodeCur, ptsk->inodeDst);
      if (distLook < distBest)
      {
         distBest = distLook;
         ptskDeliver = ptsk;
      }
   }
   if (ptskDeliver->rankDrop == -1)
      ptskDeliver->rankDrop = (*pctskOrderDrop)++;
   return ptskDeliver->inodeDst;
}

#pragma mark -
// annealing functions

_RandomizeOrder
static void _RandomizeOrder(long iTry, long cTry, long ctsk, 
         long cnode, const long paitskOrderOld[], 
         long paitskOrderNew[])
{
   // copy the old to the new
   BlockMove(paitskOrderOld, paitskOrderNew, 
            sizeof(paitskOrderNew[0])*(ctsk+cnode));
   // swap some pairs of elements
long cpairSwap = 1 + (ctsk + cnode) * (cTry-iTry)/(4*cTry);
   while (cpairSwap- >= 0)
   {
      long itsk1, itsk2;
      // swap tasks or nodes?
      if (URand(ctsk + cnode) < ctsk)
      {
         // swap tasks
         itsk1 = URand(ctsk);
         itsk2 = URand(ctsk-1);
      }
      else
      {
         // swap nodes
         itsk1 = ctsk + URand(cnode);
         itsk2 = ctsk + URand(cnode-1);
      }
      if (itsk2 >= itsk1)
         ++itsk2;
      
      long itskT = paitskOrderNew[itsk1];
      paitskOrderNew[itsk1] = paitskOrderNew[itsk2];
      paitskOrderNew[itsk2] = itskT;
   }
}
 // utilities for translation to inode problem
#pragma mark -

_InodeFromNode
// find the index to the specified Node
static long _InodeFromNode(Node node)
{
   long iinodeMin, iinodeLast;
   
   iinodeMin = 0;
   iinodeLast = s_cnode - 1;
   
   while (iinodeMin < iinodeLast)
   {
      long iinodeMid = (iinodeMin + iinodeLast + 1)/2;
      
      if (s_pdnnode[iinodeMid].node > node)
         iinodeLast = iinodeMid - 1;
      else
         iinodeMin = iinodeMid;
   }
   
   return s_pdnnode[iinodeMin].inode;
}

_CmpEnodeNode
// compare two ENODE entries by their node values for HeapSort
static int _CmpEnodeNode(INDEX i1, INDEX i2, void *pv)
{
   ENODE *pdnnode = (ENODE *)pv;
   
   return pdnnode[i1].node - pdnnode[i2].node;
}
// compare two ENODE entries by their inode values for HeapSort
static int _CmpEnodeInode(INDEX i1, INDEX i2, void *pv)
{
   ENODE *pdnnode = (ENODE *)pv;
   
   return pdnnode[i1].inode - pdnnode[i2].inode;
}

#pragma mark -

_FTakeStep
static int _FTakeStep(long inodeDst, long cactMax, 
         Action paact[], long *pcact, long *pinodeCur, long *pdist)
{
   if (*pcact >= cactMax)
   {
      printf("OOM in _FTakeStep\n");
      return fFalse;
   }
   
   long dist;
   if (!_FConnectedNodes(*pinodeCur, inodeDst, &dist))
      return fFalse;

   *pdist += dist;
   *pinodeCur = inodeDst;
   Action *pact = &paact[(*pcact)++];
   pact->action = kMoveTo;
   pact->node = s_panode[inodeDst];
   return fTrue;
}

_FGrabObject
static int _FGrabObject(long cactMax, Action paact[], 
         long *pcact, long *pwgtCarry, long *pcobjCarry, 
         long inode, long itsk)
{
   if (*pcact >= cactMax)
   {
      printf("OOM in _FGrabObject\n");
      return fFalse;
   }
   
   Action *pact = &paact[(*pcact)++];
   TSK *ptsk = &s_patsk[itsk];
   
   pact->action = kPickUpObject;
   pact->object = ptsk->itaskObject;
   
   ptsk->inodeCur = -1;
   s_pdnnode[inode].cobj -= 1;
   
   ++(*pcobjCarry);
   *pwgtCarry += ptsk->wgt;
   return fTrue;
}

_FDropObject
static int _FDropObject(long cactMax, Action paact[], 
            long *pcact, long *pwgtCarry, long *pcobjCarry, 
            long inode, long itsk)
{

   if (*pcact >= cactMax)
   {
      printf("OOM in _FDropObject\n");
      return fFalse;
   }
   
   Action *pact = &paact[(*pcact)++];
   TSK *ptsk = &s_patsk[itsk];
   
   pact->action = kDropOffObject;
   pact->object = ptsk->itaskObject;
   
   ptsk->inodeCur = inode;
   if (ptsk->inodeDst != inode)
      s_pdnnode[inode].cobj += 1;
   
   -(*pcobjCarry);
   *pwgtCarry -= ptsk->wgt;

   return fTrue;
}

#pragma mark -

_MapConnections
static void _MapConnections(long cconn, const Connection paconnection[])
{
   s_cconn = cconn;
   
   try
   {
      s_paconn = new CONN[cconn];
      
      Assert(s_pacmap == NULL);
      s_pacmap = new CMAP[s_cnode*s_cnode];
      for (long iT = s_cnode*s_cnode; -iT >= 0; )
      {
         s_pacmap[iT].distDirect = -1;
         s_pacmap[iT].distPath = -1;
      }
      
      s_panodc = new NODC[s_cnode];
   }
   catch(...)
   {
         printf("Bob, I need more memory, somewhere 
                                                      around %ld bytes\n",
          sizeof(CONN)*cconn
         +sizeof(CMAP)*s_cnode*s_cnode
         +sizeof(NODC)*s_cnode
         );
   }
   
   for (long iconn = 0; iconn < cconn; ++iconn)
   {
      CONN *pconn = &s_paconn[iconn];
      const Connection *pconnection = &paconnection[iconn];
      
      pconn->dist = pconnection->distance;
      pconn->inode1 = _InodeFromNode(pconnection->node1);
      pconn->inode2 = _InodeFromNode(pconnection->node2);
      
      s_pacmap[pconn->inode1*s_cnode + pconn-
                                                   >inode2].distDirect = 
               pconn->dist;
      s_pacmap[pconn->inode2*s_cnode + pconn-
                                                   >inode1].distDirect = 
               pconn->dist;
   }
}

_FreeConnectionMap
static void _FreeConnectionMap()
{
   if (s_paconn != NULL)
   {
      delete s_paconn;
      s_paconn = NULL;
   }
   if (s_pacmap != NULL)
   {
      delete s_pacmap;
      s_pacmap = NULL;
   }
   if (s_panodc != NULL)
   {
      delete s_panodc;
      s_panodc = NULL;
   }
}

_FConnectedNodes
static int _FConnectedNodes(long inode1, long inode2, 
            long *pdist)
{
   long distT;
   if (pdist == NULL)
      pdist = &distT;
   *pdist = s_pacmap[inode1*s_cnode + inode2].distDirect;
   return *pdist != -1;
}

_ComputeNodeDistances
static void _ComputeNodeDistances(long inode)
{
   if (s_pacmap[inode*s_cnode + inode].distPath == -1)
      _CnodeFindMinPath(inode == 0 ? 1 : 0, inode, NULL);
}

_CnodeFindMinPath
static long _CnodeFindMinPath(long inodeStart, long inodeEnd, 
               long painodePath[])
{
   if (inodeStart == inodeEnd)
      return 0;
   // clear the NODC array
   for (long inode = 0; inode < s_cnode; ++inode)
   {
      s_panodc[inode].distFromStart = distMax;
      s_panodc[inode].fCheckNeighbors = fFalse;
   }
   
   // seed the fill with the end node
   s_panodc[inodeEnd].distFromStart = 0;
   s_panodc[inodeEnd].fCheckNeighbors = fTrue;
   
   long distPathKnown = s_pacmap[inodeStart*s_cnode + 
               inodeEnd].distPath;

   // expand out from base node until we've exhaused all possibilities
   for (int fExpanded = fTrue; fExpanded; )
   {
      fExpanded = fFalse;
      
      for (long inodeSrc = 0; inodeSrc < s_cnode; ++inodeSrc)
      {
         if (!s_panodc[inodeSrc].fCheckNeighbors)
            continue;
      for (long inodeDst = 0; inodeDst < s_cnode; ++inodeDst)
         {
            long dist;
            if (inodeSrc == inodeDst || 
                  !_FConnectedNodes(inodeSrc, inodeDst, &dist))
               continue;
            if (s_panodc[inodeSrc].distFromStart + dist < 
                        s_panodc[inodeDst].distFromStart)
            {
               s_panodc[inodeDst].distFromStart = 
                     s_panodc[inodeSrc].distFromStart + dist;
               s_panodc[inodeDst].fCheckNeighbors = fTrue;
               
               if (inodeDst == inodeStart && distPathKnown != -1)
                  if (s_panodc[inodeDst].distFromStart == 
                                                            distPathKnown)
                     goto LHavePath;
               fExpanded = fTrue;
            }
         }
         s_panodc[inodeSrc].fCheckNeighbors = fFalse;
      }
   }

   // if we need to, record the results for this node
   if (s_pacmap[inodeEnd*s_cnode + inodeEnd].distPath == -1)
   {
      for (long inodeConnect = 0; inodeConnect < s_cnode; 
                     ++inodeConnect)
      {
         long dist = s_panodc[inodeConnect].distFromStart;
         s_pacmap[inodeConnect*s_cnode + inodeEnd].distPath = dist;
      }
      s_pacmap[inodeEnd*s_cnode + inodeEnd].distPath = 0;
   }
   // walk from the start node to the end node
LHavePath:
   if (s_panodc[inodeStart].distFromStart == distMax)
   {
      printf("Hey! There's no way to get from node %ld to node %ld!\n", 
      s_panode[inodeStart], s_panode[inodeEnd]);
      return 0;
   }
   
   long cnodePath;
   long inodeCur;
   for (cnodePath = 0, inodeCur = inodeStart; 
                     inodeCur != inodeEnd; ++cnodePath)
   {
      long inodeNext;
      long distConnect;
      long distCur = s_panodc[inodeCur].distFromStart;
      for (inodeNext = 0; inodeNext < s_cnode; ++inodeNext)
         if (_FConnectedNodes(inodeNext, inodeCur,                                                                   
         &distConnect) && 
               s_panodc[inodeNext].distFromStart + distConnect == 
                           s_panodc[inodeCur].distFromStart)
            break;
      
      if (painodePath != NULL)
         painodePath[cnodePath] = inodeNext;
      inodeCur = inodeNext;
   }
   
   return cnodePath;
}

_InodeNearestTask
static long _InodeNearestTask(long inodeCur)
{
   // find the nearest object
   long distBest = distMax;
   long inodeBest = -1;
   for (long inodeLook = 0; inodeLook < s_cnode; ++inodeLook)
   {
      if (s_pdnnode[inodeLook].cobj == 0)
         continue;
      
      long dist = _DistNodeToNode(inodeCur, inodeLook);
      if (dist < distBest)
      {
         inodeBest = inodeLook;
         distBest = dist;
      }
   }
   
   return inodeBest;
}

#pragma mark -

_ResetState
static void _ResetState()
{
   
   // fill in object counts in dnnode
   for (long itsk = 0; itsk < s_ctsk; ++itsk)
   {
      TSK *ptsk = &s_patsk[itsk];

      ptsk->inodeCur = ptsk->inodeStart;
      if (ptsk->inodeCur != ptsk->inodeDst)
         s_pdnnode[ptsk->inodeCur].cobj += 1;
      
      // chain the records together
      ptsk->ptskNext = ptsk+1;
   }
   
   // set up the pointers at the start and end of the list
   s_ptskFirst = s_patsk;
   s_patsk[s_ctsk-1].ptskNext = NULL;
}

_PtskRemoveTs
static TSK *_PtskRemoveTsk(TSK *ptsk)
{
   TSK **pptsk = &s_ptskFirst;
   while ((*pptsk) != ptsk)
      pptsk = &(*pptsk)->ptskNext;
   
   TSK *ptskNext = ptsk->ptskNext;
   ptsk->ptskNext = NULL;
   *pptsk = ptskNext;
   return ptskNext;
}

#pragma mark -

URand
// return a random number in the range [0, uMax)
// NOTE: this only works for values that fit into a short
static unsigned short URand(unsigned short uMac)
{
   unsigned short u, uLim;
   
   // remove bias toward small numbers
#define wRandMax 0xFFFF
   Assert(sizeof(int) > sizeof(short));
   Assert(uMax < wRandMax);
   Assert(wRandMax > 0 && (wRandMax+1) > wRandMax);
   uLim = wRandMax - ((wRandMax+1) % uMac);
   do
   {
      u = (unsigned short)Random();
   } while (u > uLim);
      
   return u % uMac;
}

// heap sort code

static void _Swap(INDEX i1, INDEX i2, void *pv, int cbFoo);

HeapSort
void HeapSort(void *prgfoo, INDEX iMac, int cbFoo, PFNCMP pfncmp)
{
   INDEX iTop, iLast, iUnder, iCur;
   
   if (iMac == 0)
      return;
   
   iTop = iMac/2;       /* first initial line worker */
   iLast = iMac - 1;   /* the last element */
   
   for(;;)
   {
      if (iTop > 0)
      {
         /* hire a new supervisor, put him in his place */
         -iTop;
      }
      else
      {
         /* retire the chairman of the board,
         /* trickle the last line worker into his correct spot
         /**/
         _Swap(iLast, 0, prgfoo, cbFoo);
         
         if (iLast- <= 1)
            return;
      }
         
      iCur = iTop;            /* new supervisor */
      iUnder = iCur + iCur + 1;      /* first underling */
      
      while (iUnder <= iLast)
      {
         /* compare to the better underling */
         if (iUnder < iLast)
            if ((*pfncmp)(iUnder, iUnder+1, prgfoo) < 0)
               ++iUnder;
         if ((*pfncmp)(iCur, iUnder, prgfoo) < 0)            
         {
            /* promote the underling */
            _Swap(iCur, iUnder, prgfoo, cbFoo);
            
            /* check the demoted "supervisor" against his new underlings */
            iCur = iUnder;
            iUnder += iUnder + 1; /* first underling of demoted supervisor */
         }
         else
         {
            /* we're done sifting, terminate loop */
            break;
         }
      }
   }
}

_Swap
static void _Swap(INDEX i1, INDEX i2, void *pv, int cbFoo)
{
   char *pb1, *pb2, bT;
   int cb;
   pb1 = (char*)pv + (long)i1*cbFoo;
   pb2 = (char*)pv + (long)i2*cbFoo;

   for (cb = cbFoo; cb-; )
   {
      bT = *pb1;
      *pb1++ = *pb2;
      *pb2++ = bT;
   }
}
 
AAPL
$105.22
Apple Inc.
+0.39
MSFT
$46.13
Microsoft Corpora
+1.11
GOOG
$539.78
Google Inc.
-4.20

MacTech Search:
Community Search:

Software Updates via MacUpdate

Ember 1.8.2 - Versatile digital scrapboo...
Ember (formerly LittleSnapper) is your digital scrapbook of things that inspire you: websites, photos, apps or other things. Just drag in images that you want to keep, organize them into relevant... Read more
Tonality Pro 1.1.2 - Professional-grade...
Tonality Pro gives you the power to create stunning and dramatic black & white images. This is a complete monochrome image editor with more than 150 one-click style presets, totally unique... Read more
VueScan 9.4.49 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
OS X Server 4.0 - For OS X 10.10 Yosemit...
Designed for OS X and iOS devices, OS X Server makes it easy to share files, schedule meetings, synchronize contacts, develop software, host your own website, publish wikis, configure Mac, iPhone,... Read more
TotalFinder 1.6.12 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
BusyCal 2.6.3 - Powerful calendar app wi...
BusyCal is an award-winning desktop calendar that combines personal productivity features for individuals with powerful calendar sharing capabilities for families and workgroups. BusyCal's unique... Read more
calibre 2.7 - Complete e-library managem...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
Skitch 2.7.3 - Take screenshots, annotat...
With Skitch, taking, annotating, and sharing screenshots or images is as fun as it is simple.Communicate and collaborate with images using Skitch and its intuitive, engaging drawing and annotating... Read more
Delicious Library 3.3.2 - Import, browse...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
Art Text 2.4.8 - Create high quality hea...
Art Text is an OS X application for creating high quality textual graphics, headings, logos, icons, Web site elements, and buttons. Thanks to multi-layer support, creating complex graphics is no... Read more

Latest Forum Discussions

See All

Rami Ismail Opens Up distribute​() for D...
Rami Ismail Opens Up distribute​() for Developers Posted by Jessica Fisher on October 24th, 2014 [ permalink ] Rami Ismail, Chief Executive of Business and Development at indie game studio | Read more »
Great Hitman GO Goes on Sale and Gets Ne...
Great Hitman GO Goes on Sale and Gets New Update – Say That Three Times Fast Posted by Jessica Fisher on October 24th, 2014 [ permalink ] | Read more »
Rival Stars Basketball Review
Rival Stars Basketball Review By Jennifer Allen on October 24th, 2014 Our Rating: :: RESTRICTIVE BUT FUNUniversal App - Designed for iPhone and iPad Rival Stars Basketball is a fun mixture of basketball and card collecting but its... | Read more »
Rubicon Development Makes Over a Dozen o...
Rubicon Development Makes Over a Dozen of Their Games Free For This Weekend Only Posted by Jessica Fisher on October 24th, 2014 [ permalink ] | Read more »
I Am Dolphin Review
I Am Dolphin Review By Jennifer Allen on October 24th, 2014 Our Rating: :: NEARLY FIN-TASTICUniversal App - Designed for iPhone and iPad Swim around and eat nearly everything that moves in I Am Dolphin, a fun Ecco-ish kind of game... | Read more »
nPlayer looks to be the ultimate choice...
Developed by Newin Inc, nPlayer may seem like your standard video player – but is aiming to be the best in its field by providing high quality video play performance and support for a huge number of video formats and codecs. User reviews include... | Read more »
Fighting Fantasy: Caverns of the Snow Wi...
Fighting Fantasy: Caverns of the Snow Witch Review By Jennifer Allen on October 24th, 2014 Our Rating: :: CLASSY STORYTELLINGUniversal App - Designed for iPhone and iPad Fighting Fantasy: Caverns of the Snow Witch is a sterling... | Read more »
A Few Days Left (Games)
A Few Days Left 1.01 Device: iOS Universal Category: Games Price: $3.99, Version: 1.01 (iTunes) Description: Screenshots are in compliance to App Store's 4+ age rating! Please see App Preview for real game play! **Important: Make... | Read more »
Toca Boo (Education)
Toca Boo 1.0.2 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0.2 (iTunes) Description: BOO! Did I scare you!? My name is Bonnie and my family loves to spook! Do you want to scare them back? Follow me and I'll... | Read more »
Intuon (Games)
Intuon 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Join the battle with your intuition in a new hardcore game Intuon! How well do you trust your intuition? Can you find a needle in a... | Read more »

Price Scanner via MacPrices.net

Weekend sale: 13-inch 128GB MacBook Air for $...
Best Buy has the 2014 13-inch 1.4GHz 128GB MacBook Air on sale for $849.99, or $150 off MSRP, on their online store. Choose free home shipping or free local store pickup (if available). Price valid... Read more
Nimbus Note Cross=Platform Notes Utility
Nimbus Note will make sure you never forget or lose your valuable data again. Create and edit notes, save web pages, screenshots and any other type of data – and share it all with your friends and... Read more
NewerTech’s Snuglet Makes MagSafe 2 Power Con...
NewerTech has introduced the Snuglet, a precision-manufactured ring designed to sit inside your MagSafe 2 connector port, providing a more snug fit to prevent your power cable from unintentional... Read more
Apple Planning To Sacrifice Gross Margins To...
Digitimes Research’s Jim Hsiao says its analysts believe Apple is planning to sacrifice its gross margins to save its tablet business, which has recently fallen into decline. They project that Apple’... Read more
Who’s On Now? – First Instant-Connect Search...
It’s nighttime and your car has broken down on the side of the highway. You need a tow truck right away, so you open an app on your iPhone, search for the closest tow truck and send an instant... Read more
13-inch 2.5GHz MacBook Pro on sale for $949,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $949.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $150 off MSRP. Price is... Read more
Save up to $125 on Retina MacBook Pros
B&H Photo has the new 2014 13″ and 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels... Read more
Apple refurbished Time Capsules available sta...
The Apple Store has certified refurbished Time Capsules available for up to $60 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $255... Read more
Textilus New Word, Notes and PDF Processor fo...
Textilus is new word-crunching, notes, and PDF processor designed exclusively for the iPad. I haven’t had time to thoroughly check it out yet, but it looks great and early reviews are positive.... Read more
WD My Passport Pro Bus-Powered Thunderbolt RA...
WD’s My Passport Pro RAID solution is powered by an integrated Thunderbolt cable for true portability and speeds as high as 233 MB/s. HighlightsOverviewSpecifications Transfer, Back Up And Edit In... Read more

Jobs Board

*Apple* Solutions Consultant - Apple Inc. (U...
…important role that the ASC serves is that of providing an excellent Apple Customer Experience. Responsibilities include: * Promoting Apple products and solutions Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.