// Dictionary implemented with a sorted array-based list
template <class Key, class Elem, class Comp, class getKey>
class SALdict : public Dictionary<Key, Elem, Comp, getKey> {
private:
  SAList<Elem, Comp, getKey>* list;

public:
  SALdict(int size=DefaultListSize)      // Constructor
    { list = new SAList<Elem, Comp, getKey>(size); }

  ~SALdict() { delete list; }            // Destructor
  void clear() { list->clear(); }        // Reinitialize
  bool insert(const Elem& e) { return list->insert(e); }

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

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

  bool find(const Key& K, Elem& e) const { // Binary search
    int l = -1;
    int r = list->leftLength() + list->rightLength();
    while (l+1 != r) { // Stop when l and r meet
      int i = (l+r)/2; // Check middle of remaining subarray
      list->setPos(i);
      list->getValue(e);
      if (Comp::lt(K, getKey::key(e))) r = i; // In left
      if (Comp::eq(K, getKey::key(e))) return true;
      if (Comp::gt(K, getKey::key(e))) l = i; // In right
    }
    return false;
  }

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