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
$102.50
Apple Inc.
+0.25
MSFT
$45.43
Microsoft Corpora
+0.55
GOOG
$571.60
Google Inc.
+2.40

MacTech Search:
Community Search:

Software Updates via MacUpdate

VueScan 9.4.41 - 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
Cloud 3.0.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
LibreOffice 4.3.1.2 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
SlingPlayer Plugin 3.3.20.505 - Browser...
SlingPlayer is the screen interface software that works hand-in-hand with the hardware inside the Slingbox to make your TV viewing experience just like that at home. It features an array of... Read more
Get Lyrical 3.8 - Auto-magically adds ly...
Get Lyrical auto-magically add lyrics to songs in iTunes. You can choose either a selection of tracks, or the current track. Or turn on "Active Tagging" to get lyrics for songs as you play them.... Read more
Viber 4.2.2 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Cocktail 7.6 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
LaunchBar 6.1 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... 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
BBEdit 10.5.12 - Powerful text and HTML...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Qube Kingdom – Tips, Tricks, Strategies,...
Qube Kingdom is a tower defense game from DeNA. You rally your troops – magicians, archers, knights, barbarians, and others – and fight against an evil menace looking to dominate your kingdom of tiny squares. Planning a war isn’t easy, so here are a... | Read more »
Qube Kingdom Review
Qube Kingdom Review By Nadia Oxford on August 29th, 2014 Our Rating: :: KIND OF A SQUARE KINGDOMUniversal App - Designed for iPhone and iPad Qube Kingdom has cute visuals, but it’s a pretty basic tower defense game at heart.   | Read more »
Fire in the Hole Review
Fire in the Hole Review By Rob Thomas on August 29th, 2014 Our Rating: :: WALK THE PLANKUniversal App - Designed for iPhone and iPad Seafoam’s Fire in the Hole looks like a bright, 8-bit throwback, but there’s not enough booty to... | Read more »
Alien Creeps TD is Now Available Worldwi...
Alien Creeps TD is Now Available Worldwide Posted by Ellis Spice on August 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Dodo Master Review
Dodo Master Review By Jordan Minor on August 29th, 2014 Our Rating: :: NEST EGGiPad Only App - Designed for the iPad Dodo Master is tough but fair, and that’s what makes it a joy to play.   | Read more »
Motorsport Manager Review
Motorsport Manager Review By Lee Hamlet on August 29th, 2014 Our Rating: :: MARVELOUS MANAGEMENTUniversal App - Designed for iPhone and iPad Despite its depth and sense of tactical freedom, Motorsport Manager is one of the most... | Read more »
Motorsport Manager – Beginner Tips, Tric...
The world of Motorsport management can be an unforgiving and merciless one, so to help with some of the stress that comes with running a successful race team, here are a few hints and tips to leave your opponents in the dust. | Read more »
CalPal Update Brings the App to 2.0, Add...
CalPal Update Brings the App to 2.0, Adds Lots of New Stuff Posted by Ellis Spice on August 29th, 2014 [ permalink ] | Read more »
Baseball Battle Review
Baseball Battle Review By Jennifer Allen on August 29th, 2014 Our Rating: :: SIMPLE HITTINGUniversal App - Designed for iPhone and iPad Simple and cute, Baseball Battle is a fairly fun baseball game for those looking for something... | Read more »
Checkmark 2.1 Update Released, and it’s...
Checkmark 2.1 Update Released, and it’s on Sale for a Limited Time Posted by Jessica Fisher on August 29th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

Labor Day Weekend MacBook Pro sale; 15-inch m...
B&H Photo has the new 2014 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 Desktop... Read more
Labor Day Weekend iPad mini sale; $50 to $100...
Best Buy has the iPad mini with Retina Display (WiFi models) on sale for $50 off MSRP on their online store for Labor Day Weekend. Choose free shipping or free local store pick up. Price is for... Read more
13-inch 1.4GHz MacBook Air on sale for $899,...
Adorama has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. Read more
It’s Official: Apple Issues Invitations To Se...
Apple has issued one of its characteristically cryptic press invitations for a special event to be held at the Flint Center for the Performing Arts in hometown Cupertino on Sept. 9, 2014 at 10:00 am... Read more
Tablet Shipments To See First On-year Decline...
TrendForce analyst Caroline Chen notes that when the iPad launched in 2010, it was an instant hit and spurred a tablet PC revolution, with tablets so popular that that notebook PC sales stagnated and... Read more
SOBERLINK Releases Apple iOS Compatible Handh...
Cypress, California based SOBERLINK, Inc., creator of the first handheld Breathalyzer designed to improve recovery outcomes, continues to show prominence in the mobile alcohol monitoring space with... Read more
New 21″ 1.4GHz iMac on sale again for $999, s...
Best Buy has the new 21″ 1.4GHz iMac on sale for $999.99 on their online store. Their price is $100 off MSRP. Choose free shipping or free local store pick up. Price is for online orders only, in-... Read more
Smartphone Outlook Remains Strong for 2014, U...
According to a new mobile phone forecast from the International Data Corporation (IDC) Worldwide Quarterly Mobile Phone Tracker, more than 1.25 billion smartphones will be shipped worldwide in 2014,... Read more
Save up to $60 with Apple refurbished iPod to...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Many, but not all... Read more
12-Inch MacBook Air Coming in 4Q14 or 2015 –...
Digitimes’ Aaron Lee and Joseph Tsai report that according to Taiwan-based upstream supply chain insiders, Apple plans to launch a thinner MacBook model either at year end 2014 or in 2015, and that... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.