// Dictionary implemented with an unsorted array-based list
template <class Key, class Elem, class Comp, class getKey>
class UALdict : public Dictionary<Key, Elem, Comp, getKey> {
private:
  AList<Elem>* list;

public:
  UALdict(int size=DefaultListSize)   // Constructor
    { list = new AList<Elem>(size); }

  ~UALdict() { delete list; }         // Destructor

  void clear() { list->clear(); }     // Reinitialize

  // Insert an element
  bool insert(const Elem& e) { return list->append(e); }

  // Use sequential search to find the element to remove
  bool remove(const Key& K, Elem& e) {
    for(list->setStart(); list->getValue(e); list->next())
      if (Comp::eq(K, getKey::key(e))) {
        list->remove(e);
        return true;
      }
    return false;
  }

  bool removeAny(Elem& e) { // Remove the last element
    if (size() == 0) return false;
    list->setEnd();
    list->prev();    // Back up to access last element
    list->remove(e);
    return true;
  }

  // Find using sequential search
  bool find(const Key& K, Elem& e) const {
    for(list->setStart(); list->getValue(e); list->next())
      if (Comp::eq(K, getKey::key(e))) return true;
    return false;
  }

  int size() // Return list size
    { return list->leftLength() + list->rightLength(); }
};