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
$524.94
Apple Inc.
+5.93
MSFT
$40.01
Microsoft Corpora
-0.39
GOOG
$536.10
Google Inc.
-20.44

MacTech Search:
Community Search:

Software Updates via MacUpdate

Mac DVDRipper Pro 4.1.7 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
PDFpenPro 6.2 - Advanced PDF toolkit for...
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Create... Read more
PDFpen 6.2 - Edit and annotate PDFs with...
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more
Monolingual 1.5.9 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. It requires a 64-bit capable Intel-based Mac and at least... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Starcraft II: Wings of Liberty 1.1.1.180...
Download the patch by launching the Starcraft II game and downloading it through the Battle.net connection within the app. Starcraft II: Wings of Liberty is a strategy game played in real-time. You... Read more
Sibelius 7.5.0 - Music notation solution...
Sibelius is the world's best-selling music notation software for Mac. It is as intuitive to use as a pen, yet so powerful that it does most things in less than the blink of an eye. The demo includes... Read more
Typinator 5.9 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
MYStuff Pro 2.0.16 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
TurboTax 2013.r17.002 - Manage your 2013...
TurboTax guides you through your tax return step by step, does all the calculations, and checks your return for errors and overlooked deductions. It lets you file your return electronically to get... Read more

Latest Forum Discussions

See All

Zynga Launches Brand New Farmville Exper...
Zynga Launches Brand New Farmville Experience with Farmville 2: Country Escape Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
David. Review
David. Review By Cata Modorcea on April 18th, 2014 Our Rating: :: MINIMALISTIC IN A DIFFERENT WAYUniversal App - Designed for iPhone and iPad David is a minimalistic game wrapped inside of a soothing atmosphere in which the hero... | Read more »
Eyefi Unveils New Eyefi Cloud Service Th...
Eyefi Unveils New Eyefi Cloud Service That Allows Users to Share Media Across Personal Devices Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
Tales from the Dragon Mountain: The Lair...
Tales from the Dragon Mountain: The Lair Review By Jennifer Allen on April 18th, 2014 Our Rating: :: STEADY ADVENTURINGiPad Only App - Designed for the iPad Treading a safe path, Tales from the Dragon Mountain: The Lair is a... | Read more »
Yahoo Updates Flickr App with Advanced E...
Yahoo Updates Flickr App with Advanced Editing Features and More Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
My Incredible Body - A Kid's App to...
My Incredible Body - A Kid's App to Learn about the Human Body 1.1.00 Device: iOS Universal Category: Education Price: $2.99, Version: 1.1.00 (iTunes) Description: Wouldn’t it be cool to look inside yourself and see what was going on... | Read more »
Trials Frontier Review
Trials Frontier Review By Carter Dotson on April 18th, 2014 Our Rating: :: A ROUGH LANDINGUniversal App - Designed for iPhone and iPad Trials Frontier finally brings the famed stunt racing franchise to mobile, but how much does its... | Read more »
Evernote Business Notebook by Moleskin I...
Evernote Business Notebook by Moleskin Introduced – Support Available in Evernote for iOS Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
Sparkle Unleashed Review
Sparkle Unleashed Review By Jennifer Allen on April 18th, 2014 Our Rating: :: CLASSY MARBLE FLINGINGUniversal App - Designed for iPhone and iPad It’s a concept we’ve seen before, but Sparkle Unleashed is a solidly enjoyable orb... | Read more »
Tilt to Live 2: Redonkulus Receives its...
Tilt to Live 2: Redonkulus Receives its First Update – Gets New Brimstone Pinball DLC Posted by Rob Rich on April 18th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

iMacs on sale for up to $160 off MSRP this we...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
iPad Airs on sale this weekend for up to $100...
Best Buy has WiFi iPad Airs on sale for $50 off MSRP and WiFi + Cellular iPad Airs on sale for $100 off MSRP on their online store for a limited time, with prices now starting at $449. Choose free... Read more
Apple restocks refurbished Mac minis starting...
The Apple Store has restocked Apple Certified Refurbished Mac minis for up to $150 off the cost of new models. Apple’s one-year warranty is included with each mini, and shipping is free: - 2.5GHz Mac... Read more
Hyundai Brings Apple CarPlay To The 2015 Sona...
Hyundai Motor America has announced it will bring Apple CarPlay functionality to the 2015 Sonata. CarPlay is pitched as a smarter, safer and easier way to use iPhone in the car and gives iPhone users... Read more
Updated iPads Coming Sooner Than We Had Thoug...
MacRumors, cites KGI securities analyst Ming Chi Kuo, well-respected as an Apple product prognisticator, saying that Apple will introduce an upgraded iPad Air and iPad mini in 2014/Q3, meaning the... Read more
Toshiba Unveils New High And Low End Laptop M...
Toshiba has announced new laptop models covering both the high-end and low-end of the notebook computer spectrum. Toshiba 4K Ultra HD Laptop Toshiba’s new Satellite P55t features one of the world’s... Read more
Save up to $270 with Apple refurbished 13-inc...
The Apple Store has Apple Certified Refurbished October 2013 13″ Retina MacBook Pros available starting at $1099, with models up to $270 off MSRP. Apple’s one-year warranty is standard, and shipping... Read more
Apple now offering refurbished iPad mini with...
The Apple Store has Certified Refurbished 2nd generation iPad minis with Retina Displays now available starting at $339. Apple’s one-year warranty is included with each model, and shipping is free.... Read more
Microsoft Blinks – Drops Microsoft Office 365...
Microsoft has dropped the annual subscription fee for Microsoft Office 365 Personal – which is needed in order to create and edit documents in Microsoft Office for iPad. However, Apple’s iOS and OS X... Read more
New AVG Vault Apps for iOS and Android Help K...
AVG Technologies N.V. an online security company for 177 million active users, has announced the launch of its latest mobile application, AVG Vault. The free app introduces an innovative user... Read more

Jobs Board

*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
*Apple* Retail - Manager - Holyoke - Apple I...
Job Summary Keeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you’re a master of them all. In the store’s fast-paced, Read more
*Apple* Retail - Manager - Apple (United Sta...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic 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
*Apple* Retail - Market Leader - Cincinnati...
…challenges of developing individuals, building teams, and affecting growth across Apple Stores. You demonstrate successful leadership ability - focusing on excellence Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.