aippandemonium.cpp

aiParts is a set of C++ classes that can be used to develop artificial intelligence for multi-decisi

//**********************************************************************
//  aipPandemonium.cpp  -  function bodies for aipPandemonium.h
//
//  Copyright (c)  2005, 2008  Brian Marshall
//
//  See the license at end of this file.
//
//  Developers/Contributers:
//    [BRM] Brian Marshall - Calgary - [e-mail]
//
//  08/01/28  [BRM] removed delete_demon(), changed ownership scheme;
//                  pandemoniums can be ordered
//  05/11/09  [BRM] pandemonium can now add demon without owning it
//  05/11/01  [BRM] made pandemonium a queue (rather than a stack)
//  05/10/28  [BRM] Fixed implied pointer to int conversion
//  05/09/10  [BRM] development began
//
//----------------------------------------------------------------------

#include "aipPandemonium.h"

//======================================================================
//  aipDemon

//  All function bodies are in the header file.

//======================================================================
//  aipPandemonium

//----------------------------------------------------------------------
//  Constructor

aipPandemonium::aipPandemonium () {

  m_first = m_last = 0;
  m_num_demon = 0;
  m_is_distinct = 0;

}


//----------------------------------------------------------------------
//  Destructor

aipPandemonium::~aipPandemonium () {

  while (m_first) {

    if (m_first->next()) {
      m_first = m_first->next();
      delete m_first->prev();
    } else {
      delete m_first;
      m_first = 0;
    }

  }

}

//----------------------------------------------------------------------
//  add  -  add a demon to the pandemonium
//
//  if this is a distinct list of ordered deomons, and the new demon
//  keys match those of a demon already in the list, the new demon
//  will be deleted.

void aipPandemonium::add (aipDemon *demon) {

  if (!demon) return;

  int is_duplicate = 0;

  int is_ordered = demon->num_keys() > 0;

  aipDemonLink * new_link = new aipDemonLink (demon, 0, 0);
  if (!new_link) return;

  if (!m_first) {                                  // list is empty

    m_first = m_last = new_link;

  } else if ( is_ordered && is_distinct() &&
              ( new_link->is_equal_to(m_first) ||
                new_link->is_equal_to(m_last) ) ) {

    is_duplicate = 1;

  } else if ( !is_ordered ||
              !(new_link->less_than(m_last)) ) {   // add at end

    m_last->set_next(new_link);
    new_link->set_prev(m_last);
    m_last = new_link;

  } else if ( new_link->less_than(m_first) ) {     // add at start

    new_link->set_next(m_first);
    m_first->set_prev(new_link);
    m_first = new_link;

  } else {   // list has at least 2 links

    aipDemonLink *nxt_link = m_first->next();
    while ( nxt_link->less_than(new_link) ) {
      nxt_link = nxt_link->next();
    }

    if ( is_ordered && is_distinct() &&
         nxt_link->is_equal_to(new_link) ) {
      is_duplicate = 1;
    } else {
      new_link->set_next(nxt_link);
      new_link->set_prev(nxt_link->prev());
      nxt_link->prev()->set_next(new_link);
      nxt_link->set_prev(new_link);
    }

  }

  if (is_duplicate) {
    delete new_link;     // and the demon
  } else {
    m_num_demon++;
  }

}

//----------------------------------------------------------------------
//  take_msg  -  take a message and maybe do something because of it

void aipPandemonium::take_msg (aipMsg *m) {

  aipDemonItr itr(this);

  for ( aipDemon *d =itr.first(); d; d=itr.next() ) {
    d->take_msg(m);
  }

}

//======================================================================
//  aipDemonLink  -  a link in a doubly-linked-list
//
//----------------------------------------------------------------------
//  Constructor

aipDemonLink::aipDemonLink (aipDemon *demon, 
                            aipDemonLink *prev, aipDemonLink *next) {

  m_demon = demon;
  m_prev  = prev;
  m_next  = next;

  if ( demon->is_owned() ) {
    m_is_owner = 0;
  } else {
    m_is_owner = 1;
    demon->set_is_owned();
  }

}

//----------------------------------------------------------------------
//  Destructor

aipDemonLink::~aipDemonLink () {

  if (m_is_owner && m_demon) delete m_demon;

}

//----------------------------------------------------------------------
//  less_than  -  return 1 (true) if this is less than the argument

int aipDemonLink::less_than (aipDemonLink *y) {

  if (!y) return 0;

  aipDemon *xdemon = this->demon();
  aipDemon *ydemon =    y->demon();

  long nkey = m_demon->num_keys();
  if (ydemon->num_keys() < nkey) nkey = ydemon->num_keys();
  if (nkey < 1 || nkey > 4) return 0;  // nkey==0 means not ordered

  if ( xdemon->key1() < ydemon->key1() ) return 1;
  if ( xdemon->key1() > ydemon->key1() ) return 0;

  if (nkey < 2) return 0;

  if ( xdemon->key2() < ydemon->key2() ) return 1;
  if ( xdemon->key2() > ydemon->key2() ) return 0;

  if (nkey < 3) return 0;

  if ( xdemon->key3() < ydemon->key3() ) return 1;
  if ( xdemon->key3() > ydemon->key3() ) return 0;

  if (nkey < 4) return 0;

  if ( xdemon->key4() < ydemon->key4() ) return 1;
//  if ( xdemon->key4() > ydemon->key4() ) return 0;

  return 0;

}

//----------------------------------------------------------------------
//  is_equal_to  -  return 1 (true) if this is equal to the argument

int aipDemonLink::is_equal_to (aipDemonLink *y) {

  if (!y) return 0;

  aipDemon *xdemon = this->demon();
  aipDemon *ydemon =    y->demon();

  long nkey = m_demon->num_keys();
  if (ydemon->num_keys() < nkey) nkey = ydemon->num_keys();
  if (nkey < 1 || nkey > 4) return 0;  // nkey==0 means not ordered

  if ( xdemon->key1() != ydemon->key1() ) return 0;

  if (nkey < 2) return 1;

  if ( xdemon->key2() != ydemon->key2() ) return 0;

  if (nkey < 3) return 1;

  if ( xdemon->key3() != ydemon->key3() ) return 0;

  if (nkey < 4) return 1;

  if ( xdemon->key4() != ydemon->key4() ) return 0;

  return 1;

}

//======================================================================
//  aipDemonItr  -  an iterator through the demons in a pandemonium

//----------------------------------------------------------------------
//  first  -  return a pointer to the first demon in the list
//              (and the current link is set to the first link)
//  Return zero if the list is empty.

aipDemon * aipDemonItr::first () {

  m_current = first_link();

  return ( m_current ? m_current->demon() : 0);

}

//----------------------------------------------------------------------
//  last  -  return a pointer to the last demon in the list
//              (and the current link is set to the last link)
//  Return zero if the list is empty.

aipDemon * aipDemonItr::last () {

  m_current = last_link();

  return ( m_current ? m_current->demon() : 0);

}

//----------------------------------------------------------------------
//  next  - return a pointer to the next demon in the list
//            (and the link to this demon becomes the current link)
//  Return zero if there is no next demon in the list.
//  If this is the first call to next() and first() has not been
//  called, it is equivalent to calling first().

aipDemon * aipDemonItr::next () {

  m_current = m_current ? m_current->next() : first_link();

  return (m_current ? m_current->demon() : 0 );

}

//----------------------------------------------------------------------
//  prev  - return a pointer to the previous demon in the list
//            (and the link to this demon becomes the current link)
//  Return zero if there is no previous demon in the list.
//  If this is the first call to prev() and last() has not been
//  called, it is equivalent to calling last().

aipDemon * aipDemonItr::prev () {

  m_current = m_current ? m_current->prev() : last_link();

  return (m_current ? m_current->demon() : 0 );

}

//----------------------------------------------------------------------
//  find  - return a pointer to the next demon in the list
//            that match the passed keys
//            (and the link to this demon becomes the current link)
//  Note that find() starts the search from the current link;
//  if there is no current-link (ex. this is the first call to find()
//  and first() has not been called), first() will be called, 
//  and the search begins at the start of the list.
//  Return zero if a matching demon is not found.

aipDemon * aipDemonItr::find (long akey1, long akey2, 
                              long akey3, long akey4) {

  if (!m_current) m_current = first_link();

  while (m_current) {
    if ( keys_match (akey1, akey2, akey3, akey4) ) break;
    m_current = m_current->next();
  }

  return (m_current ? m_current->demon() : 0 );

}

//----------------------------------------------------------------------
//  keys_match  - return true if the keys of the current demon 
//                  match the passed keys.
//  Return zero if there is no current demon or if the demon
//  has fewer keys than the passed keys.

int aipDemonItr::keys_match (long akey1, long akey2, 
                             long akey3, long akey4) {

  if (!m_current) return 0;

  if (m_current->demon()->num_keys() < 1) return 0;

  if (m_current->demon()->key1() != akey1) return 0;

  if (akey2 > -99999999) {
    if (m_current->demon()->num_keys() < 2) return 0;
    if (m_current->demon()->key2() != akey2) return 0;
  }

  if (akey3 > -99999999) {
    if (m_current->demon()->num_keys() < 3) return 0;
    if (m_current->demon()->key3() != akey3) return 0;
  }

  if (akey4 > -99999999) {
    if (m_current->demon()->num_keys() < 4) return 0;
    if (m_current->demon()->key4() != akey4) return 0;
  }

  return 1;

}

//======================================================================
//                           License
//
//   Permission is hereby granted, free of charge, to any 
//   person obtaining a copy of this software and associated 
//   documentation files (the "Software"), to deal in the Software 
//   without restriction, including without limitation the rights 
//   to use, copy, modify, merge, publish, distribute, sublicense, 
//   and/or sell copies of the Software, and to permit persons to 
//   whom the Software is furnished to do so, subject to the 
//   following conditions:
//
//   The copyright notice and this license shall be included in all 
//   copies or substantial portions of the Software.
//
//   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
//   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
//   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
//   NON-INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
//   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
//   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
//   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
//   OTHER DEALINGS IN THE SOFTWARE.
//
//
//**********************************************************************